package com.sheng.leetcode.year2023.month07.day07;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author liusheng
 * @date 2023/07/07
 * <p>
 * 2532. 过桥的时间<p>
 * <p>
 * 共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，<p>
 * 数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。<p>
 * 一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。<p>
 * 开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：<p>
 * 从左岸（新仓库）跨过桥到右岸（旧仓库），用时 leftToRighti 分钟。<p>
 * 从旧仓库选择一个箱子，并返回到桥边，用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。<p>
 * 从右岸（旧仓库）跨过桥到左岸（新仓库），用时 rightToLefti 分钟。<p>
 * 将箱子放入新仓库，并返回到桥边，用时 putNewi 分钟。不同工人可以同时放下所选的箱子。<p>
 * 如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：<p>
 * leftToRighti + rightToLefti > leftToRightj + rightToLeftj<p>
 * leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j<p>
 * 工人通过桥时需要遵循以下规则：<p>
 * 如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。<p>
 * 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。<p>
 * 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。<p>
 * 如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。<p>
 * 所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]<p>
 * 输出：6<p>
 * 解释：<p>
 * 从 0 到 1 ：工人 2 从左岸过桥到达右岸。<p>
 * 从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。<p>
 * 从 2 到 6 ：工人 2 从右岸过桥到达左岸。<p>
 * 从 6 到 7 ：工人 2 将箱子放入新仓库。<p>
 * 整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]<p>
 * 输出：50<p>
 * 解释：<p>
 * 从 0 到 10 ：工人 1 从左岸过桥到达右岸。<p>
 * 从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。<p>
 * 从 10 到 11 ：工人 0 从左岸过桥到达右岸。<p>
 * 从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。<p>
 * 从 20 到 30 ：工人 1 从右岸过桥到达左岸。<p>
 * 从 30 到 40 ：工人 1 将箱子放入新仓库。<p>
 * 从 30 到 31 ：工人 0 从右岸过桥到达左岸。<p>
 * 从 31 到 39 ：工人 0 将箱子放入新仓库。<p>
 * 从 39 到 40 ：工人 0 从左岸过桥到达右岸。<p>
 * 从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。<p>
 * 从 49 到 50 ：工人 0 从右岸过桥到达左岸。<p>
 * 从 50 到 58 ：工人 0 将箱子放入新仓库。<p>
 * 整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。<p>
 * <p>
 * 提示：<p>
 * 1 <= n, k <= 10^4<p>
 * time.length == k<p>
 * time[i].length == 4<p>
 * 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/time-to-cross-a-bridge">2532. 过桥的时间</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2532 {

    @Test
    public void test01() {
//        int n = 1, k = 3;
//        int[][] time = {{1, 1, 2, 1}, {1, 1, 3, 1}, {1, 1, 4, 1}};
        int n = 3, k = 2;
        int[][] time = {{1, 9, 1, 8}, {10, 10, 10, 10}};
        System.out.println(new Solution().findCrossingTime(n, k, time));
    }
}

class Solution {
    public int findCrossingTime(int n, int k, int[][] time) {
        int[][] t = new int[k][5];
        for (int i = 0; i < k; ++i) {
            int[] x = time[i];
            t[i] = new int[]{x[0], x[1], x[2], x[3], i};
        }
        Arrays.sort(t, (a, b) -> {
            int x = a[0] + a[2], y = b[0] + b[2];
            return x == y ? a[4] - b[4] : x - y;
        });
        int cur = 0;
        PriorityQueue<Integer> waitInLeft = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> waitInRight = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<int[]> workInLeft = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> workInRight = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < k; ++i) {
            waitInLeft.offer(i);
        }
        while (true) {
            while (!workInLeft.isEmpty()) {
                int[] p = workInLeft.peek();
                if (p[0] > cur) {
                    break;
                }
                waitInLeft.offer(workInLeft.poll()[1]);
            }
            while (!workInRight.isEmpty()) {
                int[] p = workInRight.peek();
                if (p[0] > cur) {
                    break;
                }
                waitInRight.offer(workInRight.poll()[1]);
            }
            boolean leftToGo = n > 0 && !waitInLeft.isEmpty();
            boolean rightToGo = !waitInRight.isEmpty();
            if (!leftToGo && !rightToGo) {
                int nxt = 1 << 30;
                if (!workInLeft.isEmpty()) {
                    nxt = Math.min(nxt, workInLeft.peek()[0]);
                }
                if (!workInRight.isEmpty()) {
                    nxt = Math.min(nxt, workInRight.peek()[0]);
                }
                cur = nxt;
                continue;
            }
            if (rightToGo) {
                int i = waitInRight.poll();
                cur += t[i][2];
                if (n == 0 && waitInRight.isEmpty() && workInRight.isEmpty()) {
                    return cur;
                }
                workInLeft.offer(new int[]{cur + t[i][3], i});
            } else {
                int i = waitInLeft.poll();
                cur += t[i][0];
                --n;
                workInRight.offer(new int[]{cur + t[i][1], i});
            }
        }
    }
}
